/**
 * @file LevelOrderOperate.c
 * @desc 实现二叉树的层序遍历操作（包含队列的定义与基本操作）
 * @author WangBlue (wangjiping596@gmail.com)
 * @date 2025/10/13 14:53
 * @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//============================================================
//                一、结构体定义部分
//============================================================

/**
 * @brief 二叉树结点结构
 * @note 包含数据域和左右孩子指针
 */
typedef struct BinNode {
    int data;               ///< 节点数据
    struct BinNode* lChild; ///< 左子树指针
    struct BinNode* rChild; ///< 右子树指针
} BinNode, *BinTree;

/**
 * @brief 队列节点结构（用于层序遍历）
 * @note 队列中存放的是二叉树结点指针
 */
typedef struct QueueNode {
    BinNode* treeNode;      ///< 队列中保存的树结点
    struct QueueNode* next; ///< 指向下一个队列节点
} QueueNode;

/**
 * @brief 链式队列结构
 * @note 通过 front 和 rear 指针管理队列的头尾
 */
typedef struct queue {
    QueueNode *rear;  ///< 队尾指针
    QueueNode *front; ///< 队头指针
} queue;


//============================================================
//                二、队列基本操作部分
//============================================================

/**
 * @brief 初始化队列
 * @param q 指向队列的指针
 * @note 初始化时头尾都置为 NULL
 */
void initQueue(queue *q) {
    q->front = q->rear = NULL;
}

/**
 * @brief 判断队列是否为空
 * @param q 指向队列的指针
 * @return 若队列为空返回 true，否则返回 false
 */
bool isEmpty(queue *q) {
    return (q->front == NULL || q->rear == NULL);
}

/**
 * @brief 创建一个新的队列结点
 * @param treeNode 要保存的二叉树结点指针
 * @return 返回新建的队列节点指针，若分配失败返回 NULL
 */
QueueNode * createQueue(BinNode *treeNode) {
    QueueNode *newNode = (QueueNode *) malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        printf("Queue node allocation failed!\n");
        return NULL;
    }
    newNode->treeNode = treeNode;
    newNode->next = NULL;
    return newNode;
}

/**
 * @brief 创建二叉树结点
 * @param value 节点存储的数据
 * @return 返回新建树节点的指针
 */
BinTree createNode(int value) {
    BinTree newNode = (BinTree) malloc(sizeof(BinNode));
    if (newNode == NULL) {
        printf("Tree node allocation failed!\n");
        return NULL;
    }
    newNode->data = value;
    newNode->lChild = NULL;
    newNode->rChild = NULL;
    return newNode;
}

/**
 * @brief 入队操作
 * @param q 指向队列的指针
 * @param treeNode 要入队的二叉树结点指针
 * @note 若队列为空则同时修改头尾指针
 */
void enQueue(queue *q, BinNode *treeNode) {

    // 创建新的队列结点
    QueueNode *queueNode = createQueue(treeNode);
    if (queueNode == NULL) {
        printf("Enqueue failed: node creation failed.\n");
        return;
    }

    // 若队列为空，front 和 rear 都指向新节点
    if (q->rear == NULL) {
        q->rear = queueNode;
        q->front = queueNode;
    }
    // 否则将新节点接到队尾，并更新 rear 指针
    else {
        q->rear->next = queueNode;
        q->rear = queueNode;
    }
}

/**
 * @brief 出队操作
 * @param q 指向队列的指针
 * @return 返回队头的树结点指针，若为空返回 NULL
 */
BinNode* deQueue(queue *q) {
    if (isEmpty(q)) {
        return NULL;
    }

    // 暂存队头节点并移动 front 指针
    QueueNode *temp = q->front;
    q->front = q->front->next;

    // 保存返回的树结点
    BinNode *node = temp->treeNode;

    // 若出队后队列为空，rear 也需置空
    if (!q->front) {
        q->rear = NULL;
    }

    free(temp);
    return node;
}

/**
 * @brief 打印队列中的所有元素（调试用）
 * @param q 指向队列的指针
 */
void printQueue(queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }

    QueueNode *cur = q->front;
    printf("Current queue elements: ");
    while (cur) {
        printf("%d ", cur->treeNode->data);
        cur = cur->next;
    }
    printf("\n");
}


//============================================================
//                三、二叉树遍历操作部分
//============================================================

/**
 * @brief 前序遍历（递归）
 * @param root 二叉树根结点
 * @note 访问顺序：根 → 左子树 → 右子树
 */
void preOrder(BinNode *root) {
    if (!root) {
        return;
    }
    printf("%d ", root->data);
    preOrder(root->lChild);
    preOrder(root->rChild);
}

/**
 * @brief 层序遍历（使用队列实现）
 * @param root 二叉树根结点
 * @note
 *   1. 利用队列先进先出特性实现 BFS
 *   2. 遍历顺序：从上到下、从左到右
 *   3. 时间复杂度 O(n)，空间复杂度 O(n)
 */
void levelOrder(BinNode *root) {
    if (!root) {
        return;
    }

    // 初始化队列并将根节点入队
    queue q;
    initQueue(&q);
    enQueue(&q, root);

    // 循环出队 + 访问 + 将左右子节点入队
    while (!isEmpty(&q)) {
        BinNode* deNode = deQueue(&q);
        printf("%d ", deNode->data);

        if (deNode->lChild) {
            enQueue(&q, deNode->lChild);
        }
        if (deNode->rChild) {
            enQueue(&q, deNode->rChild);
        }
    }
    printf("\n");
}


//============================================================
//                四、主函数测试部分
//============================================================
int main() {
    // 构建测试用的完全二叉树
    //            1
    //         /     \
    //        2       3
    //       / \     / \
    //      4   5   6   7
    BinTree root = createNode(1);
    root->lChild = createNode(2);
    root->rChild = createNode(3);
    root->lChild->lChild = createNode(4);
    root->lChild->rChild = createNode(5);
    root->rChild->lChild = createNode(6);
    root->rChild->rChild = createNode(7);

    printf("Level-order traversal:\n");
    levelOrder(root);

    return 0;
}
